Many computer graphics based systems, such as computer games, virtual reality systems, animation, and simulation programs, represent objects independently moving. Such systems must determine the interaction between different objects, including when contact is made. For example, when two objects collide, the forces between the objects may define subsequent motion. Various procedures have been developed to determine the interactions.
Collision detection, a principal part of motion processing, is a central problem in many computer graphics applications. It is becoming more important with the rise of new applications in virtual reality, simulation, and physically based animation. For polyhedral models specified by a boundary representation, the algorithms fall into two main categories: feature-based and simplex-based. Both varieties use coherence to obtain sublinear performance when objects move continuously through space.
The features of a polyhedron are the vertices, edges, and faces forming its boundary. Feature-based algorithms perform geometric computations on these elements to determine if a pair of polyhedra are disjoint and possibly to compute the distance between them. One example is Baraff's algorithm, discussed in D. Baraff, "Curved Surfaces and Coherence For Non-Penetrating Rigid Body Simulation", Computer Graphics, pages 19-28 (Aug. 1990), which maintains a separating plane that embeds a face of one of the polyhedra, or one edge from each polyhedra. The polyhedra are disjoint if and only if such a separating plane can be found. The separating plane is cached from one invocation of the process to the next.
The Lin-Canny closest features algorithm, described in Ming C. Lin, "Efficient Collision Detection for Animation and Robotics," PhD Thesis, University of California, Berkeley, December 1993, is a more sophisticated feature-based algorithm that computes the distance between disjoint polyhedra. It has traditionally been considered among the fastest solutions for this problem, and is included in a software package known as I-Collide. The I-Collide collision detection package uses the Lin-Canny algorithm to perform the low-level collision checks. The algorithm tracks and caches the closest features between a pair of convex polyhedra. Once these features are known, the closest points between them, and therefore between the polyhedra, can be determined.
Lin-Canny has two principal drawbacks. The first is that it does not handle the case of penetrating polyhedra. If presented with such an instance, the termination criteria are never satisfied, and the algorithm will cycle forever. To prevent this, implementations of the Lin-Canny algorithm stop cycling when a maximum iteration count is reached. The iteration count is an arbitrary threshold not strictly related to the specific structures involved. Usually, it must be set by trial and error to achieve acceptable results. In order to be accurate, the iteration count must be sufficiently high to permit terminable calculations with many cycles. With a high iteration count, the process of determining an endless cycle is slow. The system also does not return any measure of penetration depth. Thus, the usefulness of the Lin-Canny method is limited in determining exact collision times by root-finding methods, and detecting collisions among nonconvex polyhedra using standard hierarchical techniques. The second drawback is the lack of robustness of the Lin-Canny algorithm. Cycling behavior also occurs in geometrically degenerate situations, so cycle detection is not a guarantee of penetration. The algorithm can be adjusted through modification of various numerical tolerances which are interdependent in subtle ways. Choosing suitable values for all applications is difficult, if not impossible.
The difficulties in the Lin-Canny method are illustrated by the coding complexity. Much of a program implementing the Lin-Canny algorithm is devoted to correct handling of degenerate situations. Despite these problems, the relative speed of the Lin-Canny algorithm, and the general availability of the I-Collide package implementing the algorithm, have made it a popular choice for collision detection applications.
Simplex processes have other limitations. Rather than focusing on polyhedral features, simplex-based algorithms treat a polyhedron as the convex hull of a point set, and perform operations on simplices defined by subsets of these points. An algorithm (GJK) designed by Gilbert, Johnson and Keerthi and described in, "A Fast Procedure for Computing the Distance Between Complex Objects in Three-Dimensional Space," IEEE Journal of Robotics and Automation, pages 193-203, April 1988, was one of the earliest examples of this type. Given two polyhedra, the GJK algorithm searches for a simplex, defined by vertices of the Minkowski difference polyhedron, that either encloses or is nearest to the origin. If the origin is not enclosed, the distance between the origin and the nearest simplex of the difference polyhedron is equal to the distance between the original polyhedra. If the origin is enclosed, the polyhedra are penetrating, and a measure of the penetration is available.
The GJK algorithm is the essential core of an algorithm by Rich Rabbitz, discussed in "Fast Collision Detection of Moving Corvex Polyhedron", Graphic Gems IV (Heckbert, ed.), pages 133-109 (1991), which advances the original by making better use of coherence. Q-Collide is a collision detection library, spawned from I-Collide, which replaces the Lin-Canny algorithm with Rabbitz's algorithm for the low-level collision detection. All of Q-Collide's code and data structures to manage large numbers of objects are taken directly from I-Collide. Stephen Cameron has recently developed the fastest descendent of GJK, as discussed in "Enhancing GJK: Computing Minimum Penetration Distances Between Convex Polyhedra," International Conference on Robotics and Automation, IEEE (April 1997). This algorithm includes mechanisms to exploit coherence, and also uses topological vertex information to more carefully choose new simplices when the current simplices fail to satisfy the termination criteria. With these improvements, the algorithm attains the same almost-constant time complexity as Lin-Canny.